package com.example.dynamicprogramming41;

/**
 * @description 回溯算法
 * @auther lijiewei
 * @date 2022/4/9 17:33
 */
public class FlashBack {

    //最短路径
    private int minDist = Integer.MAX_VALUE;
    //路径数量矩阵
    private int[][] w = {{1,3,5,9}, {2,1,3,4}, {5,2,6,7}, {6,8,4,3}};
    //矩阵的行和列长度
    private int n = 4;
    //记录回溯的决策序列
    private int[][] tmp = new int[n][n];
    //备忘录，行列重复的选择最小的执行
    private int[][] mem = new int[n][n];

    //行
    int row = 0;
    //列
    int clo = 0;

    /**
     * 求最短路径
     * @param i 行序号
     * @param j 列序号
     * @param dist 最短路径
     * @return
     * @author lijiewei
     * @date   2022/4/9 17:37
     */
    public void minDistBt(int i, int j, int dist) {
        i = i==n ? n-1 : i;
        j = j==n ? n-1 : j;
        //到达矩阵最后一个单元格
        if (row == n && clo == n) {
            if (dist < minDist) {
                minDist = dist;
            }
            for (int i1 = 0; i1 < n; i1++) {
                for (int j1 = 0; j1 < n; j1++) {
                    System.out.print(tmp[i1][j1]+" ");
                }
                System.out.println();
            }
            System.out.println("最小路径："+minDist);
            System.out.println();
            return;
        }
        if (mem[i][j] == 0) {
            mem[i][j] = dist;
        } else if (dist >= mem[i][j]) { //行列重复的，选择最小执行
            return;
        }
        tmp[i][j] = 0 ;
        mem[i][j] = dist;
        //往下走，更新i=i+1, j=j
        if (row<n) {
            tmp[i][j] = 1;
            row = i+1;
            minDistBt(i+1, j, dist+w[i][j]);
        }
        tmp[i][j] = 0 ;
        //往右走，更新i=i,j=j+1
        if (clo<n) {
            tmp[i][j] = 1;
            clo = j+1;
            minDistBt(i, j+1, dist+w[i][j]);
        }
        tmp[i][j] = 0 ;
        row = i;
        clo = j;
    }
}
